package lsl.leetCode.year2023.test0204_Bisection;

/**
 * @author Zed
 * @description
 * @date 2023/2/4 18:43
 */
//剑指 Offer 11. 旋转数组的最小数字
public class offer11 {
    public static void main(String[] args) {
        int[] arr = {3, 1, 3};
        System.out.println(minArray(arr));
    }


    public static int minArray(int[] numbers) {
        int left = 0;
        int right = numbers.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            //问题：为什么right=mid而left=mid+1?
            //1.一般的二分查找 right=mid-1;left=mid+1;因此可以确定mid不是需要查找的元素
            if (numbers[mid] > numbers[right]) {
                //numbers[mid] > numbers[right]可以确定这时的mid所指一定不是最小值,因为一定比numbers[right]大,所以left = mid + 1;
                left = mid + 1;
            } else if (numbers[mid] < numbers[right]) {
                //numbers[mid] < numbers[right]时,mid可能指向最小值,所以right = mid
                right = mid;
            } else {
                //right--删除元素不会对结果产生影响,
                //因为这个题求唯一的最小值,只有numbers[mid]==numbers[right]时,才会指针右移删除元素,这和唯一的最小值相矛盾
                //所以right--删除的元素不是最小值
                right--;
            }
        }
        return numbers[left];
    }
}
